#include <deque>
#include <iostream>
#include <vector>

class Solution {
 public:
  Solution() : index_min_(1), array_(5 * 100000 + 100, 0) {}

  int firstMissingPositive(std::vector<int>& nums)
  {
    for (int num : nums)
    {
      if (num < 0 || num > 500000) continue;
      if (num == index_min_)
      {
        do {
          index_min_++;
        } while (array_[index_min_] != 0);
      }
      array_[num] = 1;
    }

    return index_min_;
  }

 private:
  int index_min_;
  std::deque<int> array_;
};

int main(int argc, char* argv[])
{
  Solution s;
  std::vector<int> nums{1, 2, 0};
  std::cout << s.firstMissingPositive(nums);
  return 0;
}
